题面传送门：P16981 [NWERC 2017] 安装应用 / Installing Apps
题目大意
给出一些应用下载与存储的大小和手机容量，求最多安装应用的数量与方案。
思路讲解
首先注意到题目中要素齐全：手机容量、物品占用空间等很难不把思路拉到 DP 中，尤其是背包问题。
但要注意，本题的容量会随放入物品而变化，因此在选择下载应用时也要有一定的策略，这个策略可以由贪心得到。
最后，不仅要输出拿取物品数量，还要在数量为正数时输出拿取方案。
综上，得任务列表如下：
- 贪心策略对应用预处理
- 动态规划得安装数量
- 整合拿取路径
贪心
每个应用涉及值众多，此处建议用结构体存储。
我们可以将应用分为两类，分别为 的应用与 的应用。
对于第一种应用，更为重要的肯定是存储大小，为了安装的应用尽可能多，应将 更小的应用放在前。
对于第二种应用，有多种排序方法。可以通过计算 与 的差值来排序，差值越大的排在前面。本方式可以推广到第一种应用上，因此排序规则为按 与 的差值降序排序。
由于排序方式众多，这里再展示官方的排序方法。
标准解法
bool cmp(App a, App b) { if (a.d <= a.s && b.d > b.s) return true; // a is type 1, b is type 2 if (a.d > a.s && b.d <= b.s) return false; if (a.d <= a.s && b.d <= b.s) return a.d < b.d; // Type 1: sort by d asc return a.s > b.s; // Type 2: sort by s desc (or d desc)}此处策略为：如果安装后变大或不变，按 升序排序。
如果安装后变小，按 降序排序。
后文【代码实现】部分展示的是本文中给出的非官方解法。
背包 DP
排序完成后，定义 表示考虑前 个应用，安装完 个应用后，手机至少需要多大容量。目标是找到最大的 ，使得 。
若在状态转移时沿用此思路，则需计算选定应用空间之和的最小值，计算较复杂。所以可以改变数组定义，改为前 个应用，安装完 个应用后，手机剩余空间最大值。初始化 dp[0][0]=c，其他位置值为 ，防止不剩空间与无法放入混淆。此时目标是找到最大的 ，使得 。
循环遍历每一个应用，分安装与否两种情况。转移方程如下：
注意 可为 ，若安装应加条件 。
完成 DP 后，倒序循环找出拿取数量，将此数量记为 。
路径整合
查找路径时可以在 DP 过程中，记录每个状态是由哪个状态转移而来（即选没选第 个应用）。最后从最终状态 反向回溯，即可得到安装了哪些应用，但是为倒序，需要倒序输出或翻转数组。
代码实现
完整代码
#include<bits/stdc++.h>using namespace std;int n,c,dp[505][505],num;bool b[505][505];vector<int>plan;struct data{ int d,s,m,del,pos;}a[505];bool cmp(data x,data y){ return x.del>y.del;}int main(){ cin>>n>>c; for(int i=1;i<=n;i++){ cin>>a[i].d>>a[i].s; a[i].m=max(a[i].d,a[i].s); a[i].del=a[i].d-a[i].s; a[i].pos=i; } sort(a+1,a+n+1,cmp); memset(dp,-1,sizeof(dp)); dp[0][0]=c; for(int i=1;i<=n;i++){ for(int j=0;j<=i;j++){ dp[i][j]=max(dp[i][j],dp[i-1][j]); if(j>0&&dp[i-1][j-1]>=a[i].m&&dp[i-1][j-1]-a[i].s>dp[i][j]){ dp[i][j]=dp[i-1][j-1]-a[i].s; b[i][j]=1; } } } for(int i=n;i>=0;i--){ if(dp[n][i]>=0){ num=i; break; } } cout<<num<<'\n'; if(num==0){ return 0; } for(int i=n,j=num;i>0&&j>0;i--){ if(b[i][j]==1){ plan.push_back(a[i].pos); j--; } } for(int i=plan.size()-1;i>=0;i--){ cout<<plan[i]<<' '; } return 0;}